8.4 快速排序

快速排序是一种分而治之的排序算法。它通过随机选择一个基准元素，将数组分为两部分。

一部分比基准元素小，另一部分比基准元素大，之后对两部分排序。

快速排序以其平均情况下的 O(n log n) 时间复杂度和良好的性能而广泛应用。

本节代码存放目录为 lesson20

概念与原理

快速排序的基本思想

• 选择基准元素：从数组中选择一个元素作为基准，通常选择第一个元素或最后一个元素，也可以随机选择。

• 划分数组：将数组中的其他元素与基准元素进行比较，按照小于基准和大于基准分成两部分。

• 递归排序：对基准元素两侧的子数组分别递归地进行快速排序。

• 合并结果：经过每一轮划分和递归，数组最终变得有序。

总的来说，就是选出一个元素，通过与该基准元素的对比得到两个序列，左边的序列小于基准，右边的序列大于基准。

下一步再分别针对左边、右边进行递归的快速排序，最终左边、右边也都是有序的序列。

快速排序的步骤示例

给定如下无序数组，按照从小到大排序：

[5, 3, 8, 4, 2]

通过快速排序的步骤如下：

第一步：选择基准元素

- 选择数组最后一个元素 2 作为基准，划分数组。

- 比基准小的元素：[]（没有元素小于 2）

- 比基准大的元素：[5, 3, 8, 4]

- 将基准元素 2 放在数组的正确位置，结果：[2, 3, 8, 4, 5]

第二步：递归排序

- 递归排序左侧数组（空数组，不需要处理）

- 递归排序右侧数组 [3, 8, 4, 5]

第三步：选择基准元素

- 选择 5 作为基准，划分数组。

- 比基准小的元素：[3, 4]
- 比基准大的元素：[8]

- 将基准元素 5 放在数组的正确位置，结果：[2, 3, 4, 5, 8]

第四步：递归快速排序

- 递归快速排序左侧数组 [3, 4]，选择基准 4，划分为 [3] 和 4

- 最终排序结果为 [2, 3, 4, 5, 8]

通过快速排序，数组最终被排序为 [2, 3, 4, 5, 8]。

快速排序的时间复杂度

快速排序的时间复杂度取决于基准元素的选择：

• 最坏情况：O(n²)，当基准元素总是选择最小或最大值时，导致数组无法被均匀划分。

• 最好情况：O(n log n)，当每次划分都将数组均匀地分成两半。

• 平均情况：O(n log n)，通常情况下，快速排序的表现非常接近 O(n log n)。

Go语言的实现

实现代码如下：

// partition 函数实现数组的划分
func partition(arr []int, low, high int) int {
    pivot := arr[high] // 选择最后一个元素作为基准
    i := low - 1       // i 代表已处理的元素区间

    // 遍历数组，将小于 pivot 的元素移到前面
    for j := low; j < high; j++ {
        if arr[j] < pivot {
            i++
            arr[i], arr[j] = arr[j], arr[i]
        }
    }

    // 将基准元素放到正确位置
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i + 1 // 返回基准元素的位置
}

// quickSort 实现快速排序
func quickSort(arr []int, low, high int) {
    if low < high {
        // 划分数组，并获取基准元素的位置
        pi := partition(arr, low, high)

        // 递归排序基准左侧和右侧的子数组
        quickSort(arr, low, pi-1)
        quickSort(arr, pi+1, high)
    }
}

func main() {
    arr := []int{5, 3, 8, 4, 2}
    quickSort(arr, 0, len(arr)-1)
    fmt.Println("最终排序结果: ", arr)
}

执行结果如下所示：

最终排序结果:  [2 3 4 5 8]

小结

本节我们讲解了快速排序的基本原理、步骤示例和 Go 语言的实现。

关于本节总结如下：

• 时间复杂度：快速排序的平均时间复杂度为 O(n log n)，但最坏情况下会退化为 O(n²)。

• 稳定性：快速排序是不稳定的排序算法。

• 应用场景：快速排序在处理大规模数据时非常高效，适用于数据量较大且对排序性能要求高的场景。